package com.wtgroup.demo.leetcode.org_bytedance;

/**
 * https://leetcode-cn.com/explore/featured/card/bytedance/243/array-and-sorting/1021/
 * 60. 排列序列 https://leetcode-cn.com/problems/permutation-sequence/
 * 返回第 k 个排列
 */
public class Q_排列序列 {

    public static void main(String[] args) {
        Q_排列序列 exe = new Q_排列序列();
        String res = exe.getPermutation(3, 3);
        System.out.println(res);
    }

    public String getPermutation(int n, int k) {
        char[] chars = new char[n];
        for (int i = 0; i < n; i++) {
            chars[i] = (char)((i + 1) + '0');
        }
        StringBuilder sb = new StringBuilder(n);
        String res = func(chars, 0, sb, n);
        return res;
    }

    public String func(char[] chars, int cnt, StringBuilder sb, int n) {
        if (sb.length()==n) {
            return cnt+1 ==n ? sb.toString() : null;
        }

        int len = chars.length;
        for (int i = 0; i < len; i++) {
            char c = chars[i];
            sb.append(c);
            String res = func(copyEx(chars, 0, i), cnt, sb, n);
            if (res != null) {
                return res;
            }
            sb.delete(n - chars.length, n);
            cnt++;
        }
        return null;
    }

    private char[] copyEx(char[] chars, int start, int ex) {
        char[] copy = new char[chars.length - 1];
        int j = 0;
        for (int i = start; i < chars.length; i++) {
            if (i != ex) {
                copy[j++] = chars[i];
            }
        }
        return copy;
    }
}
